/* JavaLog - package tracker 
 * 
 * Copyright (C) 2009 Allyson Lima, Diego Pedro, Victor Freire
 * 
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software 
 * Foundation, either version 3 of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
 * PARTICULAR PURPOSE. See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with this 
 * program. If not, see <http://www.gnu.org/licenses/>.
 */

package br.edu.ufcg.ccc.javalog.allshortestpath;

import java.util.ArrayList;

/**
 * FloydWarshall class
 * 
 * @author Allyson Lima, Diego Pedro, Victor Freire
 * @version 08/11/09
 */
public class FloydWarshall {

	/**
	 * Matrix distances
	 */
	private int[][] D;
	
	/**
	 * Matrix Pi
	 */
	private int[][] P;

	/**
	 * Calculates the shortest path from any pair of vertices
	 * 
	 * @param nodes
	 *            array with the vertices(starting with zero index)
	 * @param edges
	 *            array with the edges
	 */
	public void calcShortestPaths(int[] nodes, int[][] edges) {

		D = edges;
		P = new int[nodes.length][nodes.length];

		for (int k = 0; k < nodes.length; k++) {
			for (int i = 0; i < nodes.length; i++) {
				for (int j = 0; j < nodes.length; j++) {
					if (D[i][k] != Integer.MAX_VALUE
							&& D[k][j] != Integer.MAX_VALUE
							&& D[i][k] + D[k][j] < D[i][j]) {
						D[i][j] = D[i][k] + D[k][j];
						P[i][j] = nodes[k];
					}
				}
			}
		}
	}

	/**
	 * Returns shortest distance between two pairs of vertices
	 * 
	 * @param source
	 *            Source vertice
	 * @param target
	 *            Target vertice
	 * @return shortest distance between two pairs of vertices
	 */
	public int getShortestDistance(int source, int target) {
		return D[source][target];
	}

	/**
	 * Returns shortest path between two pairs of vertices
	 * 
	 * @param source
	 *            Source vertice
	 * @param target
	 *            Target vertice
	 * @return shortest path between two pairs of vertices
	 */
	public ArrayList<Integer> getShortestPath(int source, int target) {
		if (D[source][target] == Integer.MAX_VALUE) {
			return new ArrayList<Integer>();
		}
		ArrayList<Integer> path = getIntermediatePath(source, target);
		path.add(0, source);
		path.add(target);
		return path;
	}

	/**
	 * Returns intermediate shortest distance between two pairs of vertices
	 * 
	 * @param source
	 *            Source vertice
	 * @param target
	 *            Target vertice
	 * @return intermediate shortest distance between two pairs of vertices
	 */
	private ArrayList<Integer> getIntermediatePath(int source, int target) {
		if (D == null) {
			throw new IllegalArgumentException(
					"Must call calcShortestPaths(...) "
							+ "before attempting to obtain a path.");
		}
		if (P[source][target] == 0) {
			return new ArrayList<Integer>();
		}
		ArrayList<Integer> path = new ArrayList<Integer>();
		path.addAll(getIntermediatePath(source, P[source][target]));
		path.add(P[source][target]);
		path.addAll(getIntermediatePath(P[source][target], target));
		return path;
	}

}
